package _02_并查集;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/*
    通用的并查集,泛型
 */
public class GenericUnionFind<V> {
    //映射 数据作为key,节点作为value
    private Map<V,Node<V>> nodes = new HashMap<>();

    //并查集内部节点类，存放数据
    private static class Node<V>{
        V value; //数据
        Node<V> parent = this; //指向父节点,初始化时指向自己
        int rank = 1; //节点的高度,默认==1

        public Node(V value) {
            this.value = value;
        }
    }

    /*
        找到v的根节点
     */
    private Node<V> findNode(V v){
        Node<V> node = nodes.get(v);
        if(node == null) return null;

        while(!Objects.equals(node.value,node.parent.value)){
            node.parent = node.parent.parent;
            node = node.parent;
        }
        return node;
    }

    //初始化数据
    public void makeSet(V v){
        if(nodes.containsKey(v)) return;
        nodes.put(v,new Node<>(v));
    }

    //返回根节点
    public V find(V v){
        Node<V> node = findNode(v);
        return node == null ? null : node.value;
    }

    //合并两个集合
    public void union(V v1,V v2){
        Node<V> p1 = findNode(v1);
        Node<V> p2 = findNode(v2);
        if(p1 == null || p2 == null) return;
        if (Objects.equals(p1.value, p2.value)) return;

        if(p1.rank < p2.rank){
            p1.parent = p2;
        }else if(p1.rank > p2.rank){
            p2.parent = p1;
        }else{
            p1.parent = p2;
            p1.rank += 1;
        }
    }


    public boolean isSame(V v1,V v2){
        return Objects.equals(find(v1), find(v2));
    }

}
